// 假设有 n 个房子，前 n 间能偷到的最大金额是 dp[n]，前 n - 1 间能偷到的最大金额是 dp[n - 1]
// 此时向这些房子后加一间房，此房间价值为 num
// 加一间房子后，由于不能抢相邻的房子，意味着抢 n + 1 间就不能抢第 n 间，那么前 n + 1 间房能
// 偷到的最大金额是 dp[n + 1] 一定是以以下两种情况的较大值
// 1. 不抢第 n + 1 间房间，因此等于第 n 个房子的最高金额，即 dp[n + 1] = dp[n];
// 2. 抢第 n + 1 间房间，此时不能抢第 n 个房间，因此等于前 n - 1 个房子的最高金额加上当前房间
// 价值，即 dp[n + 1] = dp[n - 1] + num;

var rob = function (nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  let dp1 = new Array(nums.length).fill(0);
  let dp2 = new Array(nums.length).fill(0);
  (dp1[0] = 0), (dp2[0] = 0), (dp1[1] = nums[0]), (dp2[1] = nums[1]);
  for (let i = 2; i < nums.length; ++i) {
    dp1[i] = Math.max(dp1[i - 1], nums[i - 1] + dp1[i - 2]);
  }
  for (let i = 2; i < nums.length; ++i) {
    dp2[i] = Math.max(dp2[i - 1], nums[i] + dp2[i - 2]);
  }
  return Math.max(dp1[nums.length - 1], dp2[nums.length - 1]);
};

var rob = function (nums) {
  if (nums.length == 0) return 0;
  if (nums.length == 1) return nums[0];
  return Math.max(myRob(nums.slice(1)), myRob(nums.slice(0, -1)));
};

function myRob(nums) {
  let dp = new Array(nums.length + 1);
  dp[0] = 0;
  dp[1] = nums[0];
  for (let i = 2; i <= nums.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
  }
  return dp[nums.length];
}
